public class MyHeap {
    public void shiftDown(int[] array, int parent) {
        // child先标记parent的左孩子，因为parent可能右左没有右
        int child = 2*parent + 1;
        int size = array.length;
        while(child < size ) {
            // 如果右孩子存在，找到左右孩子中较小的孩子,用child进行标记
            if(child + 1 < size) {
                if(array[child + 1] < array[child]) {
                    child = child + 1;
                }
            }
            // 如果最小的孩子比其父亲还小，说明该结构没有满足堆的特性，进行交换
            if(array[child] < array[parent]) {
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
            } else {
                //满足就退出循环
                break;
            }
            // parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
            parent = child;
            child = 2*parent + 1;
        }
    }
}
